package com.c2b.algorithm.leetcode.jzofferII;

/**
 * <a href="https://leetcode.cn/problems/JFETK5/">二进制加法</a>
 * <p>给定两个 01 字符串 a 和 b ，请计算它们的和，并以二进制字符串的形式输出。
 * 输入为 非空 字符串且只包含数字 1 和 0。</p>
 * <pre>
 * 示例 1:
 *      输入: a = "11", b = "10"
 *      输出: "101"
 *
 *
 * 示例 2:
 *      输入: a = "1010", b = "1011"
 *      输出: "10101"
 * </pre>
 * <b>提示：</b>
 * <ui>
 * <li>每个字符串仅由字符 '0' 或 '1' 组成。</li>
 * <li>1 <= a.length, b.length <= 10^4</li>
 * <li>字符串如果不是 "0" ，就都不含前导零。</li>
 * </ui>
 *
 * @author c2b
 * @since 2023/4/10 17:30
 */
public class Jz002AddBinary_S {

    public String addBinary(String a, String b) {
        if (a == null || b == null) {
            return a == null ? b : a;
        }
        StringBuilder res = new StringBuilder();
        // 进位的标记位
        int carry = 0;
        int aIndex = a.length() - 1;
        int bIndex = b.length() - 1;
        // 只有其中一个字符串没有遍历完，就继续
        while (aIndex > -1 || bIndex > -1) {
            carry += aIndex >= 0 ? a.charAt(aIndex) - '0' : 0;
            carry += bIndex >= 0 ? b.charAt(bIndex) - '0' : 0;
            res.append(carry % 2);
            carry >>= 1;
            --aIndex;
            --bIndex;
        }
        if (carry > 0) {
            res.append('1');
        }
        return res.reverse().toString();
    }

    public static void main(String[] args) {
        Jz002AddBinary_S jz002AddBinary_s = new Jz002AddBinary_S();
        System.out.println(jz002AddBinary_s.addBinary("1", "1011"));
    }
}
